[이코테-DP]_1로 만들기
💯 solving-algo | March 30, 2021
문제 설명
아래의 연산을 이용하여 최소한의 연산 수로 1을 만들어 연산 횟수 출력
- X가 5로 나누어 떨어지면 5로 나눈다.
- X가 3로 나누어 떨어지면 3로 나눈다.
- X가 2로 나누어 떨어지면 2로 나눈다.
- X에서 1을 뺀다.
My Solution
n = int(input())
d = [0] * 30001
# 다이나믹 프로그래밍 진행(보텀업)
for i in range(2, n + 1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 현재의 수가 5으로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[n])문제 풀이
- DP테이블에 담겨 있는 값들은
%2,%3,%5이미 각각 계산했던 값들이 들어있기 때문에 최소한의 연산을 구한 값을 도출할 수 있다. - 또한 뒤에
+1를 해준 이유는 나눠줬을 때 횟수를 계산하기 위함이다. - d[1]은 0이기 때문에 d[2]부터 시작한다.
